package com.javaDemo.ti;

import com.javaDemo.node.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName: Congshanngdaoxiadayingerchashu
 * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 * @Auther: csy
 * @Date: 2020/6/5 01:18
 * @Description:
 */
public class Congshanngdaoxiadayingerchashu {

    // 使用 LinkedList<Integer> levelList 来存储每一层的节点值
    private static LinkedList<Integer> levelList;

    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) {
            queue.add(root);
        }
        while(!queue.isEmpty()) {
            // 使用 LinkedList<Integer> levelList 来存储每一层的节点值
            levelList = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                // 根据当前层数的奇偶性，决定将节点值添加到 levelList 的头部或尾部
                if(res.size() % 2 == 0) {
                    levelList.addLast(node.val); // 偶数层 -> 队列头部
                } else {
                    levelList.addFirst(node.val); // 奇数层 -> 队列尾部
                }
                // 将当前节点的左右子节点加入队列
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 将当前层的节点值列表添加到结果列表中
            res.add(levelList);
        }
        return res;
    }

    public static void main(String[] args) {
        Integer[] root = {3,9,20,null,12,15,7};
        List<List<Integer>> lists=levelOrder(TreeNode.makeTree(root));
        System.out.println();
    }
}
